package com.atguigu.LinkedList;

import java.util.Stack;

public class SingleLinkedListDemo {
    public static void main(String[] args) {

        HeroNode heroNode = new HeroNode(5, "55", "555");
        HeroNode heroNode1 = new HeroNode(1, "11", "111");
        HeroNode heroNode2 = new HeroNode(3, "33", "333");
        HeroNode heroNode3 = new HeroNode(4, "44", "444");
        SingleLinkedList singleLinkedList = new SingleLinkedList();
//        singleLinkedList.add(heroNode);
//        singleLinkedList.add(heroNode1);
//        singleLinkedList.add(heroNode2);
//        singleLinkedList.add(heroNode3);
//        更具顺序来添加
        singleLinkedList.addById(heroNode);
        singleLinkedList.addById(heroNode1);
        singleLinkedList.addById(heroNode2);
        singleLinkedList.addById(heroNode3);

//        singleLinkedList.updata(new HeroNode(1,"22","222"));
//
//        singleLinkedList.deleteNode(new HeroNode(1,"22","222"));
        System.out.println("原来链表的情况");
        singleLinkedList.list();

//        System.out.println("有效节点的个数"+getLength(singleLinkedList.getHead()));
//        System.out.println("倒数第"+findLastIndexNode(singleLinkedList.getHead(),1));
        System.out.println("反转之后");
        reserveList(singleLinkedList.getHead());
        System.out.println("逆序打印");
        reservePrint(singleLinkedList.getHead());
    }
    //使用堆的方式，逆序打印
    public static void reservePrint(HeroNode head){
        if(head.next==null){
            return;
        }
        HeroNode temp=head.next;
        Stack<HeroNode> heroNodes = new Stack<>();
        while (temp!=null){
            heroNodes.add(temp);
            temp = temp.next;
        }
        while (heroNodes.size()>0){
            System.out.println("逆序打印为"+heroNodes.pop());
        }
    }


    //反转链表
    /*
    *定义一个reserveHead=new HeroNode()
    从头到尾遍历，每遍历一次，取出尾节点放到reserveHead后面
    原来的链表
     **/

    public static void reserveList(HeroNode head){
        //只有一个或者零个节点的链表不需要反转，直接返回
        if(head.next==null||head.next.next==null){
            return;
        }
        //因为时头节点，不能动，我们使用一个辅助节点来遍历
        HeroNode temp=head.next;
        //创建temp的下一个节点
        HeroNode temp_next=null;
        //创建一个新的空节点
        HeroNode reserveHeard = new HeroNode(100, "", "");
        while (temp!=null){
            temp_next=temp.next;//保存当前节点的下一个节点
            temp.next=reserveHeard.next;//将当前节点指向新节点的下一个节点
            reserveHeard.next=temp;
            temp=temp_next;//向后走
        }
        head.next=reserveHeard.next;


        HeroNode temp_list=head.next;
        while (true){

            //判断是否到了最后一个节点
            if(temp_list==null){
                break;
            }
            System.out.println(temp_list.toString());
            //将temp_list后移动
            temp_list=temp_list.next;
        }
    }



    //查找单链表的倒数第K个节点
    /*
    * 编写一个接收头head 和index 的方法
    * index表示倒数第k个节点
    * 先把链表从头到尾遍历，得到长度
    * 得到size后，我们从链表的第一个开始遍历（size-index），就可以得到了
    * 否则返回null
    * */
    public static HeroNode findLastIndexNode(HeroNode head,int index){
        if(head.next==null){
            return null;
        }
        int size=getLength(head);
        HeroNode temp=head.next;
        if(index<=0||index>size){
            return null;
        }
        for(int i=0;i<(size-index);i++){
            temp=temp.next;
        }
        return temp;
    }


    //方法：获取到单链表的节点个数（如果带头节点，我们不统计）
    public static int getLength(HeroNode head){
        //空链表
        if(head.next==null){
            return 0;
        }
        //定义一个辅助变量
        HeroNode temp=head.next;
        int len=0;
        while (temp!=null){
            len++;
            temp=temp.next;
        }
        return len;
    }
}
//管理我们的英雄节点
class SingleLinkedList{
    //初始化一个头节点，不放置具体数
    private HeroNode head= new HeroNode(0,"","");
    public HeroNode getHead(){
        return head;
    }
    //当不考虑编号的顺序问题时，找到当前链表的最后节点，将最后节点的next指向新的节点
    public void add(HeroNode hereNode){
        //因为head节点不能动，我们需要一个辅助节点来帮助我们
        HeroNode temp=head;
        while (true){
            //为空，则代表找到了最后一个节点
            if(temp.next==null){
                break;
            }
            //否则，找到下一个节点
            temp=temp.next;
        }
        //当退出循环的时候，temp指向最后一个节点，完成添加
        temp.next=hereNode;
    }
    //根据编号的顺序添加英雄
    //我们不要使用temp指向的节点和我们要添加的节点比较，而是temp.next
    public void addById(HeroNode heroNode){

        //我们的temp是位于添加位置的前一个节点
        HeroNode temp=head;
        boolean flag=false;
        while (true){
            //我们我们的temp已经指向了最后一个节点
            if(temp.next==null){
                break;
            }
            //遍历的时候，更具他们的no值进行比较，
            if(temp.next.no>heroNode.no){//位置找到了，就在temp的后买你

                break;
            }else if(temp.next.no==heroNode.no){
                flag=true;
                break;
            }else {//位置没有找到，继续向后走
                temp = temp.next;
            }
        }
        //根据flag判断
        if(flag){
            System.out.printf("%d已经存在了",heroNode.no);
        }else{
            heroNode.next=temp.next;
            temp.next=heroNode;
        }
    }

    public void updata(HeroNode newHeroNode){
        //判断链表是否为空
        if(head.next==null){
            System.out.println("链表为空");
            return;
        }
        //用一个临时变量来作为指针
        HeroNode temp=head.next;
        //设置一个变量，表示是否找到该节点
        boolean flag=false;
        while (true){
            if(temp==null){
                break;//链表遍历结束
            }
            if(temp.no==newHeroNode.no){
                flag=true;
                break;
            }
            temp=temp.next;
        }
        //根据flag 判断是否找到要修改的节点
        if(flag){//表示已经找到了
            temp.nickname=newHeroNode.nickname;
            temp.name=newHeroNode.name;
        }else{
            System.out.printf("没有找到序号为%d的节点",newHeroNode.no);
        }
    }

    public void deleteNode(HeroNode heroNode){
        //判断链表是否为空
        if(head.next==null){
            System.out.println("链表为空");
            return;
        }
        //因为时头节点，不能动，我们使用一个辅助节点来遍历
        HeroNode temp=head;
//        设置一个标记位，判断我们是否找到了要删除的节点
        boolean flag=false;
        while (true){
            //表示已经到了链表的末尾
            if(temp.next==null){
                break;
            }
            if(temp.next.no==heroNode.no){
                flag=true;
                break;
            }
            temp=temp.next;
        }
        if(flag){
            //表示已经找到了该节点
            temp.next=temp.next.next;
        }else{
            System.out.printf("没有找到序号为%d的节点",heroNode.no);
        }

    }




    //遍历节点
    public void list(){
        //判断链表是否为空
        if(head.next==null){
            System.out.println("链表为空");
            return;
        }
        //因为时头节点，不能动，我们使用一个辅助节点来遍历
        HeroNode temp=head.next;
        while (true){

            //判断是否到了最后一个节点
            if(temp==null){
                break;
            }
            System.out.println(temp.toString());
//            将temp后移动
            temp=temp.next;
        }
    }
}

/*
* 创建节点，里面包含序号，姓名，昵称和指向下一个节点
* 每一个HeroNode就是一个节点
*
* */
class HeroNode{
    public int no;
    public String name;
    public String nickname;
    public HeroNode next;
    //创建一个节点
    public HeroNode(int no,String name,String nickname){
        this.no=no;
        this.name=name;
        this.nickname=nickname;
    }
    //为了显式节点，我们重写该方法
    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}
